algebraic data type

programming (Or "sum of products type") In functionalprogramming, new types can be defined, each of which has one

or more constructors. Such a type is known as an algebraic

data type. E.g. in Haskell we can define a new type,

"Tree":

data Tree = Empty | Leaf Int | Node Tree Tree

with constructors "Empty", "Leaf" and "Node". The

constructors can be used much like functions in that they can

be (partially) applied to arguments of the appropriate type.

For example, the Leaf constructor has the functional type Int

-@# Tree.

A constructor application cannot be reduced (evaluated) like a

function application though since it is already in normalform. Functions which operate on algebraic data types can be

defined using pattern matching:

depth :: Tree -@# Int

depth Empty = 0

depth (Leaf n) = 1

depth (Node l r) = 1 + max (depth l) (depth r)

The most common algebraic data type is the list which has

constructors Nil and Cons, written in Haskell using the

special syntax "[]" for Nil and infix ":" for Cons.

Special cases of algebraic types are product types (only one

constructor) and enumeration types (many constructors with

no arguments). Algebraic types are one kind of constructedtype (i.e. a type formed by combining other types).

An algebraic data type may also be an abstract data type

(ADT) if it is exported from a module without its

constructors. Objects of such a type can only be manipulated

using functions defined in the same module as the type

itself.

In set theory the equivalent of an algebraic data type is a

discriminated union - a set whose elements consist of a tag

(equivalent to a constructor) and an object of a type

corresponding to the tag (equivalent to the constructor

arguments).

(1994-11-23)